/* ==========================================
 * JGraphT : a free Java graph-theory library
 * ==========================================
 *
 * Project Info:  http://jgrapht.sourceforge.net/
 * Project Creator:  Barak Naveh (http://sourceforge.net/users/barak_naveh)
 *
 * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software Foundation,
 * Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 */
/* -----------------
 * CompoundPermutationIter.java
 * -----------------
 * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
 *
 * Original Author:  Assaf Lehr
 * Contributor(s):   -
 *
 * $Id: CompoundPermutationIter.java,v 1.2 2007/05/22 15:52:58 kjellw Exp $
 *
 * Changes
 * -------
 */
package org.jgrapht.experimental.permutation;

import java.util.*;

import org.jgrapht.util.*;

/**
 * For permutation like this:
 * <li>1,2 are the same eq.group (numbers)
 * <li>a,b are og the same eq.group (letters)
 * <li>'$' is of its own eq. group (signs) Let the order of the group be
 * (arbitrary): signs,numbers,letters (note that for performance reasons, this
 * arbitrary order is the worst! see Performance section below)
 * 
 * <p>
 * These are the possible compound perm: [$,1,2,a,b,c]
 * 
 * <p>
 * [$,1,2,a,c,b]
 * 
 * <p>
 * [$,1,2,b,a,c]
 * 
 * <p>
 * [$,1,2,b,c,a]
 * 
 * <p>
 * [$,1,2,c,a,b]
 * 
 * <p>
 * [$,1,2,c,b,a]
 * 
 * <p>
 * [$,2,1,a,b,c]
 * 
 * <p>
 * [$,2,1,a,c,b]
 * 
 * <p>
 * [$,2,1,b,a,c]
 * 
 * <p>
 * [$,2,1,b,c,a]
 * 
 * <p>
 * [$,2,1,c,a,b]
 * 
 * <p>
 * [$,2,1,c,b,a]
 * 
 * <p>
 * The overall number is the product of the factorials of each eq. group size;
 * in our example : (1!)x(2!)x(3!)=1x2x6=12. Using the constructor with eq.group
 * sizes and initial order [1,2,3], the result permutations are retrieved as
 * numbers in an array, where [0,1,2,3,4,5] means [$,1,2,a,b,c]:
 * 
 * <p>
 * [0,1,2,3,5,4]
 * 
 * <p>
 * [0,1,2,4,3,5]
 * 
 * <p>
 * etc. etc., till:
 * 
 * <p>
 * [0,2,1,5,4,3] means [$,2,1,c,b,a]
 * 
 * <p>
 * <p>
 * <i>Performance:</i> The implementation tries to advance each time the group
 * zero, if it does not succeed, it tries the next group (1,2 and so on), so:
 * try to put the largest group as the first groups, UNLIKE the example.
 * Performance-wise it is better to do [a,b,c,1,2,$] .The effect is improvement
 * by constant (for example, by 2)
 * 
 * @author Assaf
 * @since May 30, 2005
 */
public class CompoundPermutationIter implements ArrayPermutationsIter, Iterator {
	// ~ Instance fields
	// --------------------------------------------------------

	IntegerPermutationIter[] permArray;

	/**
	 * on the example 1+2+3=6
	 */
	private int totalPermArraySize;

	/**
	 * The overall number is the product of the factorial of each eq. group
	 * size.
	 */
	private int max;

	private int iterCounter = 0;

	// ~ Constructors
	// -----------------------------------------------------------

	/**
	 * For the class example, use [1,2,2]. order matters! (performance-wise too)
	 * 
	 * @param equalityGroupsSizesArray
	 */
	public CompoundPermutationIter(int[] equalityGroupsSizesArray) {
		init(equalityGroupsSizesArray);
	}

	// ~ Methods
	// ----------------------------------------------------------------

	/**
	 * Creates an IntegerPermutationIter class per equalityGroup with different
	 * integers.
	 * 
	 * @param equalityGroupsSizesArray
	 */
	private void init(int[] equalityGroupsSizesArray) {
		this.permArray = new IntegerPermutationIter[equalityGroupsSizesArray.length];

		int counter = 0;
		this.max = 1; // each time , multiply by factorail(eqGroupSize)
		for (int eqGroup = 0; eqGroup < equalityGroupsSizesArray.length; eqGroup++) {
			// create an array of eq.group size filled with values
			// of counter, counter+1, ... counter+size-1
			int currGroupSize = equalityGroupsSizesArray[eqGroup];
			int[] currArray = new int[currGroupSize];
			for (int i = 0; i < currGroupSize; i++) {
				currArray[i] = counter;
				counter++;
			}
			this.permArray[eqGroup] = new IntegerPermutationIter(currArray);
			this.permArray[eqGroup].getNext(); // first iteration return the
			// source

			// each time , multiply by factorail(eqGroupSize)
			this.max *= MathUtil.factorial(currGroupSize);
		}
		this.totalPermArraySize = counter;

		// calc max
	}

	public Object next() {
		return getNext();
	}

	/**
	 * Iteration may be one of these two: 1. the last group advances by one
	 * iter, all else stay. 2. the last group cannot advance , so it restarts
	 * but telling the group after it to advance (done recursively till some
	 * group can advance)
	 */
	public int[] getNext() {
		if (this.iterCounter == 0) {
			// just return it , without change
			this.iterCounter++;
			return getPermAsArray();
		}

		int firstGroupCapableOfAdvancing = -1;
		int currGroupIndex = 0; //
		while (firstGroupCapableOfAdvancing == -1) {
			IntegerPermutationIter currGroup = this.permArray[currGroupIndex];

			if (currGroup.hasNext()) {
				currGroup.getNext();

				// restart all that we passed on
				for (int i = 0; i < currGroupIndex; i++) {
					restartPermutationGroup(i);
				}
				firstGroupCapableOfAdvancing = currGroupIndex;
			}

			currGroupIndex++;
			if (currGroupIndex >= this.permArray.length) {
				break;
			}
		}

		this.iterCounter++;

		if (firstGroupCapableOfAdvancing == -1) {
			// nothing found. we finished all iterations
			return null;
		} else {
			int[] tempArray = getPermAsArray();
			return tempArray;
		}
	}

	/**
	 * Creates and returns a new array which consists of the eq. group current
	 * permutation arrays. For example, in the 10th iter ([$,2,1,b,c,a]) The
	 * permutations current statuses is [0] [2,1] [4,5,3] so retrieve
	 * [0,2,1,4,5,3]
	 */
	public int[] getPermAsArray() {
		int[] resultArray = new int[this.totalPermArraySize];
		int counter = 0;
		for (int groupIndex = 0; groupIndex < this.permArray.length; groupIndex++) {
			int[] currPermArray = this.permArray[groupIndex].getCurrent();
			System.arraycopy(currPermArray, 0, resultArray, counter,
					currPermArray.length);
			counter += currPermArray.length;
		}
		return resultArray;
	}

	/**
	 * Restarts by creating a new one instead.
	 * 
	 * @param groupIndex
	 */
	private void restartPermutationGroup(int groupIndex) {
		int[] oldPermArray = this.permArray[groupIndex].getCurrent();
		Arrays.sort(oldPermArray);
		this.permArray[groupIndex] = new IntegerPermutationIter(oldPermArray);
		this.permArray[groupIndex].getNext();
	}

	public boolean hasNext() {
		boolean result;
		if (this.iterCounter < this.max) {
			result = true;
		} else {
			result = false;
		}
		return result;
	}

	public int getMax() {
		return max;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see ArrayPermutationsIter#nextPermutation()
	 */
	public int[] nextPermutation() {
		return (int[]) next();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see ArrayPermutationsIter#hasNextPermutaions()
	 */
	public boolean hasNextPermutaions() {
		return hasNext();
	}

	/**
	 * UNIMPLEMENTED. always throws new UnsupportedOperationException
	 * 
	 * @see java.util.Iterator#remove()
	 */
	public void remove() {
		throw new UnsupportedOperationException();
	}
}

// End CompoundPermutationIter.java
